\chapter{公钥密码体制(Public Key Cryptography)}

1976年W. Diffie和N. E. Hellman发表了著名的文章“New Directions in Cryptography”，奠定了公钥密码的基础，与传统的密码系统不同的是不需要额外分发密钥的可信信道，加密密钥和解密密钥是本质上不同的，知道一个密钥不能有效地计算出来另外一个。图\ref{convetion-public-coompare}是传统加密体系和公钥加密体系框图的对比。
\begin{figure}[htbp]
	\centering
	\subfigure[\label{fig:a}]{
	   \includegraphics[width=0.7\textwidth]{conventional-crypt-sys.png}
    }
	\subfigure[\label{fig:b}]{
		\includegraphics[width=0.7\textwidth]{public-key-sys.png}
	}
	\caption{“New Directions in Cryptography”一文中传统加密和公钥加密框图比较}
	\label{convetion-public-coompare}
\end{figure}

传统密码系统与公钥密码系统最大的不同是，不要一个保密信道来传输大家共同使用的密钥，这个保密信道的构建在互联网环境下，通常很难构建，或者构建成本极高。


公钥密码体系中，信息传递者有一个私钥(SK,secrete key)和一个公钥(PK,public key)，公钥PK是公开的，现在有两个信息传递者A和B(或者是Alice:/) 和Bob:/)  )，其公私钥分别为$SK_a,PK_a,SK_b,PK_b$，这时A和B之间不需要进行密钥协商或者交换就可以进行保密通信，假如A要发信息给B，A只需要用B的公钥对信息进行加密$c=E_{PK_b}(m)$，然后把加密后的信息c发给B,B收到后，用其私钥进行解密$m=D_{SK_b}(c)$,恢复出m。\par


\section{陷门单向函数(trap-door one-way function)}
公钥密码体系的思想很好理解，但是要构造这样一个体系，并且能够抵抗住密码分析者的攻击却不是一件容易的事情，要求密码分析者从公开的各种信息中无法获得密钥信息和有效的解密办法，Diffie和Hellman在提出公钥密码思想后也给出了如何构造这种密码体系的基本方向或者方法，那就是寻找一个陷门单向函数。\par
陷门单向函数是这样一类函数族$y=f(x,k)$,其中k为参数，对于每个k，x和f(x,k)一一对应，给定x和k，f(x,k)很“容易”计算，但是若给定y(或者说f(x,k))和k，计算x是“困难”的，这就是说f(x,k)是个单向函数。\par

如果存在一个“陷门信息"$k'=d(k)$及函数g(y,k')，使得当$y=f(x,k)$时,$x=g(y,k')$，并且在给定y和k'时，$g(y,k')$是"容易"计算的，也就是说陷门信息使得给定y和k'时，可以“容易”地计算x。\par

仅仅具备单向性的函数可以用来存储口令文件(例如Hash函数)，而陷门单向函数则可以用来建立公钥密码系统.

\newpage

\section{MH方法\cite{qing-cry}}
1978年，美国斯坦福大学的R. C. Merkle和M. E. Hellman在"Hiding information and signatures in trapdoor knapsacks"一文中，建立了一种基于陷门背包的公钥密码系统。


\subsection{0-1背包问题(0-1 Knapsack Problem)}
0-1背包问题是指这样一个问题。有n件物品和容量为m的背包，知道每件物品的重量以及价值，每件物品只有一件供你选择，你可以选择装还是不装，找到一种装法，使背包里的物品重量不超过背包容量且价值最大。\par

我们看看0-1背包问题的一个变种，有n件物品和容量为m的背包，知道每件物品的重量以及价值分别为$w_i,v_i$，我们先不考虑背包容量，我们只找到一种装法使得物品价值正好为S，我们用数学语言描述，或者说构建一个数学模型，就是：\par
\vspace{1cm}
有一个正整数S和一个背包向量$V=(v_1,v_2,\ldots,v_n)$，找到一个二进制向量$X=(x_1,x_2,\ldots,x_n)$,使得$S=\sum_{i=1}^{n}x_iv_i$。\par
\vspace{1cm}

“这个问题是一个著名的NP(Non-polynomial)问题，目前解一般背包问题最好的算法需要$O(2^{n/2})$,存储量$O(2^{n/4})$。但是背包问题的困难程度和背包向量的选择关系很大，如果$V=(1,2,4,\ldots,2^{n-1})$，给定S求X就会很容易”\cite{qing-cry}。\par

上面变种的0-1背包问题中还有一种特殊背包问题，我们称为简单背包(simple knapsack),简单背包问题中的背包向量V是一个超上升(super increasing)向量,即$v_i > \sum_{j=1}^{i-1}v_j$，对于简单背包问题可以用线性时间解出，也就是说简单背包问题是个P(Polynomial)类问题。\par

下面我们分别举几个例子来看看。\par
\vspace{1cm}
\begin{example}
	$n=5,S=14,V=(1,10,5,22,3)$，我们可以检验一下，$X=(1,1,0,0,1)$是这个背包问题的一个解，因为容易算得$XV^T=1\cdot1+10\cdot1+5\cdot0+22\cdot0+3\cdot1=1+10+3=14$.\cite{Denning-cry}
\end{example}
\vspace{1cm}
\begin{example}
	我们用穷尽法计算一个背包问题，并且以此方法，看看背包问题的时间复杂度。我们有，$n=4,S=14,V=(1,10,5,3)$，我们列出所有的可能的解向量：
	\begin{align}
		&(0,0,0,1)\stackrel{\text{背包重量}}{\Longrightarrow}3,  &(0,0,1,0)\stackrel{\text{背包重量}}{\Longrightarrow}5\\
		&(0,0,1,1)\stackrel{\text{背包重量}}{\Longrightarrow}8,  &(0,1,0,0)\stackrel{\text{背包重量}}{\Longrightarrow}10\\
		&(0,1,0,1)\stackrel{\text{背包重量}}{\Longrightarrow}13, &(0,1,1,0)\stackrel{\text{背包重量}}{\Longrightarrow}15\\
		&(0,1,1,1)\stackrel{\text{背包重量}}{\Longrightarrow}18, &(1,0,0,0)\stackrel{\text{背包重量}}{\Longrightarrow}1\\
		&(1,0,0,1)\stackrel{\text{背包重量}}{\Longrightarrow}4,  &(1,0,1,0)\stackrel{\text{背包重量}}{\Longrightarrow}6\\
		&(1,0,1,1)\stackrel{\text{背包重量}}{\Longrightarrow}9,  &(1,1,0,0)\stackrel{\text{背包重量}}{\Longrightarrow}11\\
		&(1,1,0,1)\stackrel{\text{背包重量}}{\Longrightarrow}14, &(1,1,1,0)\stackrel{\text{背包重量}}{\Longrightarrow}16\\
		&(1,1,1,1)\stackrel{\text{背包重量}}{\Longrightarrow}19, &(0,0,0,0)\stackrel{\text{背包重量}}{\Longrightarrow}0
	\end{align}
	我们可以看出$X=(1,1,0,1)$是这个问题的解.\\
	我们假设背包向量长度为50，那么按上面的算法有$2^{50}$种可能向量，如果每检验一个向量用时0.1微秒($10^{-6}$秒)，则最坏情况下需要用时：
	\[(10^{-6}\cdot 2^{50})/60/60/24/365 \approx 35.7 \text{年} \]
\end{example}
\vspace{1cm}
\begin{example}
	我们看一个特殊背包向量不是困难问题的例子。我们有，$n=8,S=20,V=(1,2,2^2,2^3,2^4,2^5,2^6,2^7)$.\\
	我们计算一下看看是否有解：\\
	$
	V=(1,2,4,8,16,32,64,128)=(v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8) \\
	v_5,v_6,v_7,v_8 > S\rightarrow v_5=0,v_6=0,v_7=0,v_8=0 \\
	v_4<S \rightarrow v_4=1,S=S-v_4=20-16=4\\
	v_3>S \rightarrow v_3=0\\
	v_2 = S \rightarrow v_2=1,S=S-v_2=4-4=0\\
	v_1=0\\
	$
	通过以上计算过程，我们可以看出有解，且解向量为$X=(0,1,0,1,0,0,0,0)$，我们看到这个背包问题的实质其实就是求一个数的二进制表示，其当然是P类问题。
\end{example}
\vspace{1cm}
\begin{example}
	我们有，$n=5,S=14,V=(1,10,5,22,3)$，我们对背包向量排序得$V^{'}=(1,3,5,10,22)$,我们可以检验得知这是一个简单背包向量，他的解就很容易求得：\\
	$
	S<22 \rightarrow m_5=0\\
	S>10 \rightarrow m_4=1,S=S-10=4\\
	S<5 \rightarrow m_3=0\\
	S>3 \rightarrow m_2=1,S=S-3=1\\
	S=1 \rightarrow m_1=1,S=S-1=0\\
	$
	可知此问题有解，且解向量为$X=(0,1,0,1,0)$.
\end{example}
\vspace{1cm}

\subsection{MH方法}
\subsubsection{陷门单向函数构造}
简单背包问题是一个P类问题，MH方法的本质是将简单背包变成一个陷门背包，如果不知道陷门信息，就是一个难解问题，知道陷门，就是一个容易解的问题。\par
下面我肯看看MH实现方法。\par

首先选择一个简单背包向量$V=(v_1,v_2,\ldots,v_n)$，给定S，我们容易求得$X=(x_1,x_2,\ldots,x_n)$，使得$S=\sum_{i=1}^{n}x_iv_i$。\par

然后我们选择一个整数t，t满足$t>\sum_{i=1}^{n}v_i$,选择一个与t互素的整数p，计算$p^{-1},pp^{-1}=1 mod\ t$，我们计算一个新向量$V^{'}=pV (mod\ t)$,新向量中的元素伪随机分布,故单纯看$S=XV^{'}$是个困难问题，但是如果我们知道$p^{-1},m$，我们再可以把$S=XV^{'}$进行如下转换：
\begin{equation}
	S^{'}=p^{-1}S(mod\ t)\\
	=p^{-1}XV^{'}(mod\ t)\\
	=p^{-1}XpV(mod\ t)\\
	=p^{-1}pXV(mod\ t)\\
	=XV(mod\ t)
\end{equation}

因为$t>\sum_{i=1}^{n}v_i$，所以有$S^{'}=XV$.\par

我们知道简单背包问题是个容易计算的问题，把所以我们把求$S=XV^{'}$这个一般背包问题，转化为简单背包问题$S^{'}=XV$，其中$S^{'}=p^{-1}S(mod\ t), V=p^{-1} V^{'}$,求得X。\par
从上面的分析可以看到，把这个一般背包问题转化为简单背包问题的关键是知道$t$和$p^{-1}$，所以$(t,p^{-1})$就是私钥。

\subsubsection{加密方法}
对于MH方法，用户公布困难背包向量$V^{'}=(v_1,v_2,\ldots,v_n)$,$V^{'}$是公钥,$(V,t,p^{-1})$保密，$(t,p^{-1})$为私钥，由于V可以根据私钥和公钥计算出来，也可以不做存储或者考虑。\par
我们假设A要向B发送一个保密信息，这句话意味着，A发送的信息只想让B看到，A获得B公开发布的公钥$V^{'}$,然后将信息预处理为长度为n的二进制块$X=(x_1,x_2,\ldots,x_n)$\footnote{其实就是加密值的二进制编码}，加密过程为：
\[ C=E_{V'}(X)=\sum_{i=1}^{n}(x_iv'_i) \]
A将密文C发送给B，B收到C后的解密过程为，首先计算$C'=p^{-1}C \pmod{t}$，然后求解简单背包问题$C'=XV$。

\vspace{1cm}
\begin{example}
	我们看一个背包加密的简单的例子，我们选简单背包向量$V= \left(  1,3,5,10 \right) $,选$t>\sum_{i=1}^{4}v_i=19$,此处我们选$t=20$,选择一个与t互素的数p,我们选$p=7$,那么$p^{-1}\pmod{20}=3$,我们生成一个“困难背包”$V^{'}=pV \pmod{20}= \left(  7,1,15,10\right) $，发布公钥$\left( V^{'},t \right) $，保存好私钥$\left( V,p^{-1},t\right) $\footnote{私钥也可以写成$\left( p^{-1},t\right) $，因为可以$V=p^{-1}V^{'}$}。
	我们给定原文为13，计算密文，并写出接受放解密过程。
\end{example}
\begin{solution}
	(1)计算密文：13的二进制向量为$\left( 1,1,0,1\right) $，计算$\left( 1,1,0,1\right)V^{'T}=18$，密文为$c=18$. \\
	(2)解密：$c^{'}=p^{-1}c \pmod{20}=3\times 18 \pmod{20}=14$，计算X，$c^{'}=XV^T$，$X=\left( 1,1,0,1\right) $,X看做一个二进制向量，解密后的值为$1\times 2^3 + 1\times 2^2 + 0\times 2 +1=13$.
\end{solution}
\vspace{1cm}

\subsubsection{签名方法}

首先我们要明确的是，以下这种很自然的构造签名方法是错误的。大家可以先看看这种方法，然后思考一下错误在哪里？本小节最后将会给出错误的解释。
\par

我们假设A要向B发送一个信息X，B收到这个信息后，要有“足够的理由”相信，信息就是A发送的。\par
我们用MH方法来构造一个MH签名算法。\par
A要发送信息M给B，A用自己的私钥信息$V$对信息进行"加密"(其实这里叫“加密”已经不合适了,通常我们会说A对信息进行“签名”)：
\[ C=E_{V}(X)=\sum_{i=1}^{n}(x_iv_i) \]
然后将M和C(签名信息)，一起发送给B，记为：
\[A\rightarrow B:(M,C)\]

B首先获得了A的公钥信息$V^{'}$,在收到这个信息后用，可以验证以下等式是否成立：
\[ M \stackrel{?}{=} E_{V^{'}}(X) \]
成立表示M是A发送的，并且没有经过第三方篡改，不成立则证明这个信息不是A要发送的。从而形成一个电子签名。

\vspace{1cm}
\begin{example}
	我们依然以前一个例子为基础看看MH签名过程：\\
	私钥：$\left( V,p^{-1},t\right),V=\left(  1,3,5,10 \right),p^{-1}=3,t=20$\\
	公钥：$\left( V^{'},t \right),V^{'}=\left(  7,1,15,10\right),t=20 $\\
	要发送的消息$m=13$(十进制)，写出签名过程。
\end{example}
\begin{solution}
	我们首先用私钥计算签名值：\\
	$t_1=p^{-1}m \pmod{t}=3\times 13 \pmod{20}=19$\\
	$t_1=XV^T\rightarrow 19=X\left(1,3,5,10 \right)^T $，求解X，得$X=\left( 1,1,1,1\right) $,X看做一个二进制向量,可得签名值Sig为15.\par
	将消息13和签名值15一起发送给接收方，接收方进行如下验证：\\
	签名值Sig的二进制表示为$X'=\left( 1,1,1,1\right) $，用公钥计算$m'=\left( 1,1,1,1\right)V^{'T}=\left( 1,1,1,1\right) \left( 7,1,15,10 \right)^T =33 \pmod(20)=13$，因为$m=m'$，所以我们可以判定此消息是知道私钥的人发送的，并且消息没有被修改。
	
\end{solution}

\vspace{1cm}
\emph{从上面的例子看，好像MH方法可以构成公钥方式的数字签名(如同RSA一样)，其实不然，“陷门背包公开钥密码系统和RSA不同，不能实现数字签名，这是因为：它的加密变换不是整个信息空间上的映成函数(onto function)
\footnote{Any function is said to be onto function if,in the function,every element of codomain has one or more relative elements in the domain. Onto function is also popularly known as a surjective function.}
,因此某些信息(实际上大多数信息)不能先解密后加密，A. Shamir建立了一种不能用于加密的陷门背包数字签名系统
\footnote{卿斯汉老师的书里没有给出参考文章，从Denning的文章“Digital Signatures with RSA and Other Public Key Cryptosystems ”中给出的参考文献，可以推断，这应该是个技术报告“Shamir, A. A fast signature scheme. Tech. Rept. MIT/LCS/TM-107,	MIT Lab. for Computer Science, Cambridge, Mass., July 1978.”}
，这种经典的方法现在虽然不再应用，但其构思有许多方面值得我们借鉴。”}\cite{qing-cry}
\vspace{1cm}


\subsection{背包问题求解的发展}
1978年，斯坦福大学的Merkle和Hellman在“Hiding Information and Signatures in Trapdoor Knapsacks”文章中，提出利用背包问题设计公钥密码系统的方法。\par

"
1979年，R. Schroepple和A. Shamir 发表了一种求解一般背包问题的算法\footnote{文章名为：A $T=O(2^{n/2}),S=O(2^{n/4}) algorithm for certain NP-complete problems.$}，所需时间为$O(2^{n/2})$，存储量为$O(2^{n/4})$，当$n=100$时,$2^{50} \approx 10^{15}$,因此一个处理机大约要用11574天才能算出一个解，但是当1000个处理机并行工作时，大约12天就可以求出解(假定一个处理机每天能执行$8.64\times 10^{10}$条指令)，所以，Merkle和Hellman原先的建议不甚合适，至少应当取n=200，此时$2^{100} \approx 10^{30}$,方可保证MH公开密码系统的安全性。
"\cite{qing-cry}.\par

背包问题一直被持续研究，2010年Nick Howgrave-Graham和Antoine Joux发表了一篇文章<New generic algorithm for hard kanpsacks>，将密度为1背包问题的求解时间降为$O(2^{0.3113n})$(见图\ref{2010-knapsack}),从这篇文章的参考文献中，我们也可以看到Shamir对这个问题的持续研究(见图\ref{shamir-knapsack})，1979、1981、1983本别有成果发表。\par

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{2010-knapsack.png}
	\caption{2010年公开发表的背包算法研究}
	\label{2010-knapsack}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{shamir-knapsack.png}
	\caption{Shamir对背包算法的持续研究}
	\label{shamir-knapsack}
\end{figure}

\newpage 

\section{RSA}
1978年，美国的麻省理工学院的R. L. Rivest,A. Shamir和M. Adleman在其论文"A method for obtaining digital signatures and public-key cryptosystems"中提出了一种实现Diffie——Hellman公钥思想的方法，简称为RSA方法。\par
1982年，Rivest、Shamir和Adleman三个创始人正式成立了RSA Data Security公司，1989年刚刚发展起来的互联网采用了RSA加密软件，1994年RSA源代码在互联网上被匿名公布，RSA公司成立后不断发展，目前已是一家顶级的安全服务公司。\footnote{信息来源于\url{https://blog.csdn.net/wangjianno2/article/details/19262887}}\par
\subsection{RSA依赖的困难问题}
RSA依赖的困难问题是：整数分解为素数是个困难问题，有时候我们也称“整数分解是个困难问题”、“素分解是个计算上困难的问题”。\par
但是如果有一组素数，计算出这组素数的合数，却是一个容易的问题。\par
需要注意的是，虽然RSA计算困难问题基于的“整数分解”，但是RSA破解并不等价于“整数分解问题”，我们从下面RSA方法的介绍中可以知道，我们只是说如果能够获得整数的分解，那么就可以破解RSA，并没有证明破解RSA与“整数分解问题”计算复杂性等价。
\subsection{RSA加密方法}
\begin{enumerate}
	\item 用户选取两个不同的大素数$p$和$q$，计算$n=pq$,我们知道$\phi(n)=(p-1)(q-1)$.
	\item 选一个正整数$d$，满足$gcd(d,\phi(n))=1$.
	\item 计算d模$\phi(n)$的逆元e，也就是说$ed=1(mod\ \phi(n))$.
	\item $\left( e,n \right)$做为公钥，$\left( d,n\right)$ 做为私钥.
	\item 加密：RSA是分组加密，取一个明文分组$M$，$0 \leq M \leq n-1$\footnote{对与实际加密的数据可以按照一定方法把数据变换为符合合格要求，比如将其变为n进制编码},$C=E_e(M)=M^e(mod\ n)$。
	\item 解密：$M'=D_d(C)=C^d(mod\ n)=(M^e)^d(mod\ n)=M^{ed}(mod\ n)=M(mod\ n)$
\end{enumerate}
\par
\vspace{1cm}
已知公钥$\left( e,n \right)$，如果能够计算出$n$的素分解，也就是知道$p$和$q$，那么就能很容易计算出$d$，可见RSA算法依赖的困难问题就是分解因子问题。\par
通常在算法具体实现中，我们会在产生公私钥后，销毁$p$和$q$，如果算法设计有漏洞，泄露了$p$和$q$，这是有可能造成“侧信道攻击”(Side Channel Attack,简称SCA)\footnote{侧信道攻击，也有称为边信道攻击的，但是我比较喜欢侧信道攻击，因为，好听$\heartsuit$，通常来讲，侧信道攻击就是利用加密软件或硬件运行时通过各种“途径”产生的各种泄漏信息进行攻击。有针对密码算法的计时攻击(Timing attacks)、能量攻击(power analysis attacks)、电磁分析(EM-attacks)攻击等，也有一些比如针对键盘敲击内容的侧信道攻击，比如分析声音、电磁攻击等等，所以广义上的侧信道攻击，脑洞大开，这种攻击的主要根源在于我们通常在设计过程中，基本上考虑在“正常信道”上对攻击的对抗，而因为侧信道种类繁多，很少有系统考虑，或者及时考虑也会有遗漏}。

\subsubsection{RSA解密过程证明}
下面我们证明RSA的正确性，也就是解密过程可以获得明文$M$。\par
\begin{enumerate}
	\item $M$为明文,$C$为密文,公钥$\left(e,n \right) $.
	\item 加密：$C=M^e\pmod{n}$.
	\item 解密: $M^{'}=C^d \pmod{n}=m^{ed}\pmod{n}$.
	\item $ed=1 \pmod{\phi\left( n\right) }\Rightarrow ed=k\phi(n)+1$
	\item $M^{'}=C^d \pmod{n}=M^{ed}\pmod{n}=M^{k\phi(n)+1} \pmod{n}$
	\item $M$与$n$互素，由Euler定理$M^{\phi\left( n\right) }=1 \pmod{n}$，可得
	$M^{k \phi \left( n \right) +1} \pmod{n} = M^{k\phi\left( n \right) } M \pmod{n} = M \pmod{n}$.
	\item $M$与$n$不互素,也就是说$gcd(M,n)\neq 1$,我们知道$n$的素分解为$p,q$，那也就是意味着$M$是$p$或$q$的倍数，不失一般性，我们假设是$p$的倍数，也就是说$M=tp,t\in \mathbb{N}$，此时$M$一定不是$q$的倍数，如果$M$是$q$的倍数,那么$M$就是$n$的倍数，我们知道模$n$其实是整个运算空间的边界，也就是$M<n$，显然如果$M$就是$n$的倍数，与$M<n$矛盾，所以如果，$M$是$p$的倍数,那么一定有$gcd(M,q)=1$。
	\item $gcd(M,q)=1$，由Euler定理$M^{\phi\left( q\right) }=1 \pmod{q}$,可得，\\
	$
	M^{k \phi \left( n \right) } \pmod{q} \\
	= M^{k\phi\left( p \right)\left( q \right) } \pmod{q} \\
	= \left[ M^{k\phi\left( q \right)} \right] ^{\phi \left( p \right) } \pmod{q}\\
	=1  \pmod{q}\\
	$,也就是说，存在整数$r,M^{k \phi \left( n \right) }=1+rq$,两边同乘$M=tp$，有，
	$M^{k \phi \left( n \right) +1} = M+ rqtp=M+rtn$，从上式我们可得：$M^{k \phi \left( n \right) +1}\pmod{n} = M\pmod{n}$.[证毕]

\end{enumerate}

\subsection{RSA简单示例}

说一个RSA系统是多少位的，通常是指模n转换位二进制后是多少位，因为n的大小限定了运算空间的大小，体现了破解的难度，也可以说体现了密码系统的安全性。下面我们给出一个12位RSA的加密解密方法\footnote{此节采用的例子素材来源于https://www.jianshu.com/p/4e302869d057}。\par

\subsubsection{生成公私钥对} 
RSA是非对称加密，有公钥和私钥，公钥公开给加密方加密，私钥留给自己解密，是不公开的。\par
1.随机选两个素数，用p、q来代替 （素数的数值越大，位数就越多，可靠性就越高。假设我们取p = 47，q = 59。\par
2.计算这两个素数的乘积，$n =p \times q = 47 \times 59 = 2773$,n的长度就是公钥长度。2773写成二进制是101011010101，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。\par
3.计算n的欧拉函数$\phi(n)$,$\phi(n) = (p-1)(q-1) $,$\phi(2773) = (47 - 1) \times (59 - 1) = 46 \times 58 = 2668$.\par
4.随机选择一个整数e，$1< e < \phi(n)$，且e与$\phi(n)$ 互素（我们知道，此时$e^{\phi(n)} \equiv 1 (mod  n)$）.例如我们在1到2668之间，随机选择了17，e = 17。\par
5.计算e对于$\phi(n)$的模乘法逆元d，当$gcd(e,\phi(n)) =1$，$ed \equiv 1 (mod \ \phi(n)) \Rightarrow d = (1+k\phi(n)) / e,k \in \mathbb{Z}$,代入各值，$d=(1+2668k)/17$,可以依次给k赋值，取d为整数的序偶，得到一系列(k,d),(1,157)、(18,2825)、(35,5493) $\ldots$,随机选一个序偶，比如(1,157)，也就是d=157.\par
6.将n和e封装成公钥，n和d封装成私钥，即公钥为：n = 2773，e = 17，私钥为：n = 2773，d = 157。\par

\subsubsection{用公钥加密字符串} 
假设我们加密一个字符"A"，首先字符要用数值表示（）这就是编码，信源编码），一般用Unicode或ASCII码表示，此处我们用ASCII码表示，
"A"的ASCII码十进制为65(十六进制0x41)，我们用m来代替明文(message)，c来代替密文(cipher)，m = 65，RSA加密公式：$m^e \equiv c (mod n)$,代入各值$65^{17} (mod \ 2773) \equiv 6,599,743,590,836,592,050,933,837,890,625 (mod \ 2773) \equiv 332 (mod \ 2773),c=332$。\par

\subsubsection{用私钥解密密文}
RSA解密公式：$c^d \equiv m (mod \ n)$,代入各值，$c^d \equiv 332^{157} \equiv 6.5868707484014117339891253968203e+395 \equiv 65  (mod \ 2773),m=65$.

\subsubsection{用私钥简单签名字符串}
RSA签名消息m，$s=m^d  \pmod{n}=65^{157} \pmod{2773}=126$,签名值S为“126”，将m||s发送给接收方。
\subsubsection{用公钥验证字符串}
接收到m||s后，计算$m'=s^e \pmod{n}=126^{17} \pmod{2773}=65$，当$m'=m$，我们推断出签名值是只有知道私钥的人计算出来的，并且接受到的m没有被修改。

\subsection{公私钥对的生成}

RSA的理论很容易看明白，但是当您坐下来准备实现一个RSA算法时，我这里说的实现，不是利用OpenSSL等库来实现，这些库基本的RSA加密过程函数已实现好了，你只需要了解RSA的过程原理依次调用就可以，我们这里的实现，是指利用一些基础的数学函数库来实现RSA算法。\par

而在具体做这些底层实现时，会有很多细节问题需要考虑，首先确定好RSA系统的位数后，大素数p和q如何产生？大数如何计算？e如何产生？等等，整个过程是有很多细节需要考虑，而且在密钥产生过程中，如果考虑不够全面，对攻击者来说会有“漏”可捡，而这些要求，你对一个编程者提出来，显然是不公平的，他很难达到这样的要求，道理很简单，他不是数学家，不是密码学家，那么怎么解决？标准。这也就是说你可以看到大量的NIST FIPS和SP标准，以及RFC、ANSI标准在详细描述实现的细节，可以去看看文档"OpenSSL FIPS 140-2 Security Policy"，这里面提到OpenSSL在实现时参考的一些标准。实现细节大家可以去看这些标准，以及其他资料。\par

下面我引用一个帖子里\footnote{\url{https://stackoverflow.com/questions/18264314/generating-a-public-private-key-pair-using-an-initial-key}}的一段原文，对于RSA密钥生成会有一个宏观的了解。\par

\begin{lstlisting}
	The algorithm for generating an RSA key pair boils down to finding a set of big, prime numbers, that fulfil some algebraical properties and that are of appropriate size. If you need a 2048 bit RSA key, you will typically look for 2 prime number, each having a a rough length of 1024 bits.
	
	The process of finding a prime number is trial-and-error: you randomly pick an integer of appropriate size, and test if it is prime. If it is not, you retry.
	
	In the real world, the random generator that drives the algorithm is a deterministic PRNG which is seeded with a secret of appropriate entropy (e.g. 128 bits of true randomness).
	
	In your case, the PRNG seed can be derived from a user secret or even from another key (provided it is secret of course). Derivation should be performed with a salted KDF like HKDF, PBKDF2, etc.
	
	You don't specify which crypto library you use: whatever it is, you must be clear on how it draw randomness and how to define the seed of the PRNG.
\end{lstlisting}
从上面的讨论中，我们也可以体会到随机数生成在加密体制中是非常重要的功能，他不仅仅在流加密中。

\section{ECC(Elliptic Curve Cryptography)}

\subsection{基本概念}
椭圆曲线(elliptic curve) 是指由Weierstrass韦尔斯特拉(中文翻译有韦尔斯特拉、魏尔斯特拉斯)方程确定的平面，韦尔斯特拉方程为：$E:y^2+axy+by = x^3+cx^2+dx+e$,E是Elliptic curve的缩写，表示这个方程描述了一个椭圆曲线,其中a，b，c，d和e属于域F，F可以是有理数域、复数域、有限域，密码学中通常采用有限域。\par
下面我们用Sagemath绘制几个实数域上的椭圆曲线。\par

\begin{example}
	椭圆曲线：$y^2=x^3-2x$\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x
		p= plot(EllipticCurve([0,0,0,-2,0]),gridlines='true', xmin=-4, xmax=4, 
		ymin=-3, ymax=3,legend_label='$y^2=x^3-2x$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{EC-1.png}
		\caption{椭圆曲线$y^2=x^3-2x$\label{fig:EC-1}}
	\end{figure}
\end{example}

\begin{example}
	椭圆曲线：$y^2=x^3-2x+1$\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x
		p= plot(EllipticCurve([0,0,0,-2,1]),gridlines='true', xmin=-4, xmax=4, 
		ymin=-3, ymax=3,legend_label='$y^2=x^3-2x+1$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{EC-2.png}
		\caption{椭圆曲线$y^2=x^3-2x+1$\label{fig:EC-2}}
	\end{figure}
\end{example}



\begin{example}
	椭圆曲线：$y^2=x^3-2x+2$\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x+2
		p= plot(EllipticCurve([0,0,0,-2,2]),gridlines='true', xmin=-4, xmax=4, 
		ymin=-3, ymax=3,legend_label='$y^2=x^3-2x+2$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{EC-3.png}
		\caption{椭圆曲线$y^2=x^3-2x+2$\label{fig:EC-3}}
	\end{figure}
\end{example}

通过定义恰当的“加法”运算，椭圆曲线上的点全体构成一个加法群， 正因为椭圆曲线存在加法结构，所以它包含了很多重要的数论信息。下面我们看看椭圆曲线上的加法群的构建。\par

\begin{itemize}
	\item 单位元：$O$为单位元，椭圆曲线上的所有点$P$有$P+O=P$，$O$也是一个椭圆曲线上的一个点，是一个无穷远的点。
	\item 逆元：对点$P=(x,y)$，其加法逆元为$(x,-y)$，记为$-P$，$P+(-P)=O$，由此也可以定义减法$P-P=O$
	\item 加法：对于两个不同且不互逆的点$P,Q$,我们画一条通过$P,Q$的直线，与椭圆曲线交于一点，这个交点是唯一的(除非所做的直线是$P$或$Q$的切线)，此交点的逆元为$R$，定义$P+Q=R$。加法定义如图\ref{fig:ECC-add}所示。
	\item 倍数：点$P$的倍数定义为，在$P$点做椭圆曲线的一条切线，设切线与椭圆曲线交于一点，$R$为此交点的逆元，定义$2P=P+P=R$，一般将$\overbrace{Q+Q+\ldots+Q}^{n\text{个}Q}$记为$nQ$。
\end{itemize}
\par

可以证明以上定义的加法运算具有交换律和结合律等一般性质。\par

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{ECC-add.jpg}
	\caption{椭圆曲线加法定义图示\label{fig:ECC-add}}
\end{figure}

\subsection{有限域上的椭圆曲线}

为了简单起见，我们通常考虑在有限域$GF(p)$上的椭圆曲线，$p$为大于3的素数，在有限域$GF(p)$上的曲线$y^2=x^3+ax+b  \left( a,b\in GF(p),4a^3+27b^2\neq 0 \right) $称为有限域上的椭圆曲线，通常记为$E_p(a,b)$。\par

椭圆曲线的定义也要求曲线是非奇异的(即处处可导的)。几何上来说，这意味着图像里面没有尖点、自相交或孤立点。代数上来说，这成立当且仅当判别式$\delta =4a^3+27b^2$不等于0，这里主要是满足其可导性。
\par

我们看看同一方程在不同域上的曲线。\par

\begin{example}
	椭圆曲线：$y^2=x^3-2x$在有限域$GF(11)$和实数域上表示的曲线。\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x在有限域GF(11)
		p=plot(EllipticCurve(GF(11),[0,0,0,-2,0]),gridlines='true', 
		xmin=-11, xmax=11, ymin=-30, ymax=30,
		legend_label='$y^2=x^3-2x,GF(11)$')
		# y^2=x^3-2x在实数域 
		p+=plot(EllipticCurve([0,0,0,-2,0]),gridlines='true', color=hue(1), 
		xmin=-11, xmax=11,ymin=-30, ymax=30,legend_label='$y^2=x^3-2x$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{EC-R-GF.png}
		\caption{椭圆曲线$y^2=x^3-2x$在有限域$GF(11)$和实数域上的图\label{fig:EC-R-GF}}
	\end{figure}
\end{example}
\par

有限域椭圆曲线构成的群如下：
\begin{itemize}
	\item 单位元：$O$为单位元，椭圆曲线上的所有点$P$有$P+O=P$，$O$也是一个椭圆曲线上的一个点，是一个无穷远的点。
	\item 逆元：对点$P=(x,y)$，其加法逆元为$(x,-y)$，记为$-P$，$P+(-P)=O$，由此也可以定义减法$P-P=O$
	\item 加法：对于两个不同且不互逆的点$P(x_1,y_1),Q(x_2,y_2),x_1 \neq x_2$,$P(x_1,y_1)+Q(x_2,y_2)=S(x_3,y_3)$,其中：\\
	$x_3=\lambda ^2-x_1-x_2 \pmod{p}$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{p}$\\
	$\lambda=\dfrac{y_2-y_1}{x_2-x_1}$
	
	\item 倍数：点$P$的倍数定义为，$2P=P(x_1,y_1)+P(x_1,y_1)=S(x_3,y_3)$，其中：\\
	$x_3=\lambda ^2-2x_1 pmod{p}$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{p}$\\
	$\lambda=\dfrac{3x_1^2+a}{2y_1}$,其中$a$是方程中的常数。
\end{itemize}
\par

\textit{假设$E/F_p$是一个椭圆曲线，$e\geq 1$,如果$(x_1,y_1),x_1,y_1 \in F_{p^e}$，满足曲线方程$E$，我们说点$(x_1,y_1)$在椭圆曲线上。当$e=1$时，点$(x_1,y_1)$定义在基础域(base field)$F_p$上，当$e> 1$时，点$(x_1,y_1)$定义在域$F_p$的扩展上。在域$F_{p^e}$上曲线$E$上的所有点，包括无穷远点(the point of infinity)$O$，我们记为$E(F_{p^e})$,用$|E(F_{p^e})|$表示椭圆曲线上点的个数。}\par

\textit{根据哈赛(Hase)的研究结果，我们有$|E(F_{p^e})|=p^e+1-t$，其中$|t| \leq 2\sqrt{p^e}$，这表明$|E(F_{p^e})|$非常接近$p^e-1$。对于$E(F_{p})$来说，这个值为$p+1$.}\cite{boneh-cry}
\par

\vspace{0.5cm}
\begin{example}\cite{李浪-密码工程}
	$GF(11)$上的一个椭圆曲线$E_{11}(1,6):y^2 = x^3+x+6 \pmod{11}$构成的交换群。	
\end{example}
\begin{solution}
	1、计算椭圆曲线上所有的点
	\par
	对于$GF(11)$上的每一个点$x$计算$s=x^3+x+6 \pmod{11}$，然后求解$y^2=s \pmod{11}$，如果此方程有解(即s为模11的平方剩余)，解为$y$，则$(x,\pm y)$是$E_{11}(1,6)$上的点，按照这个方法，我们可以获得$E_{11}(1,6)$上的点，共12个点：\\
	$(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9)$
	\par
	2、交换群
	\par
	我们可以看到$(2,4)$和$(2,7)$互为逆元,下面我们计算$(2,4)+(3,5)$:\\
	$\lambda = \dfrac{y_2-y_1}{x_2-x_1} = \dfrac{5-4}{3-2} =1 $\\
	$x_3=\lambda ^2-x_1-x_2 \pmod{11}=1^2 - 2-3 \pmod{11}=7$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{11}=(2-7)-4=2$\\
	$(2,4)+(3,5)=(7,2)$,可以看到$(7,2)$仍然是椭圆曲线上的点，可见加法运算在$E_{11}(1,6)$上是封闭的。
\end{solution}
\par

\begin{example}\cite{yang-mcry}
	在$E_{23}(1,1)$上计算$P+Q,P=(3,10),Q=(9,7)$。
\end{example}
\begin{solution}
	$\lambda = \dfrac{y_2-y_1}{x_2-x_1} = \dfrac{7-10}{9-3} =\dfrac{-3}{6} =\dfrac{-1}{2}=11 \pmod{23}$ \footnote{此处计算解释，我们需要找到一个数$a,2a=1\pmod{23}$，可知$a=12,-12 \pmod{23}=11$ }\par
	$x_3=\lambda ^2-x_1-x_2 \pmod{23}=11^2 - 3-9 \pmod{23}=17$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{23}=11(3-17)-10=-164=20$\\
	$P+Q=(17,20)$,结果仍然为$E_{23}(1,1)$中的点。
\end{solution}
\par

\subsection{构造密码算法}
要想利用椭圆曲线构造密码算法，从大的方面来说，要解决以下几个问题：
\par
\begin{enumerate}
	\item 将一个信息，也就是一个二进制串或者一个数，映射到椭圆曲线的一个点，同时也可将椭圆曲线上的一个点映射到一个信息。
	\item 然后在椭圆曲线上找到一个计算困难问题，但这个困难问题当有某个信息时要变得不困难。
	\item 设计一个信息变换或计算过程。
\end{enumerate}
\par
下面我们依次看看以上这几个问题的考虑。

\subsubsection{消息到椭圆曲线上的映射}
设消息是$m,0\leq m \leq M $,$E:y^3=x^2+ax+b$，给定一个整数k，实际中k在30~50之间取值，在这里我们取k=30，对明文m计算一系列x，$x=\{mk+j,j=0,1,2,\ldots\}=\{30m+j,j=0,1,2,\ldots\}$,直到$x^2+ax+b \pmod{p}$是平方根，那么就将m映射到椭圆曲线上这一点$(x,\sqrt{x^2+ax+b})$。\par

反之，有一个椭圆曲线上的一点$(x,y)$，我们将其还原为消息m的过程为$m=\lfloor \dfrac{x}{30}\rfloor$.

\subsubsection{椭圆曲线上的计算困难问题}
在$E_p(a,b)$上考虑方程$Q=kP$，$Q,P\in E_p(a,b),k< p$,我们知道了$k,P$很容易求解$Q$，但是知道了$P,Q$，求确$k$是一个困难问题，这就是椭圆曲线上的离散对数问题。

\subsubsection{椭圆曲线上的密码算法}

\paragraph{ECC(Elliptic Curve Cryptography)加密算法}

通常软件实现采用的域为$GF(p)$域，在硬件实现的采用$GF(2^m)$域，下面我们看一个经典的$GF(p)$域上的ECC算法。\cite{高胜-blockchain}\par
ECC属于公钥密码体制，下面假设用Alice给Bob准备发送一个秘密信息的实例来说明整个过程。\par

\vspace{0.5cm}
\textbf{(1)Bob生成公私钥对}\par
\begin{itemize}
	\item 选择椭圆曲线$E:y^2=x^3+ax+b \pmod{p}$，构造群$E_p(a,b)$.
	\item 在$E_p(a,b)$上挑选生成元$g=(x_0,y_0)$,$g$应使得满足$ng=O$的最小n是一个非常大的素数。
	\item 选择一个随机数$\alpha,\alpha \in [1,n-1]$,计算$\beta=\alpha g$。
	\item Bob的公钥为$(E_p(a,b),n,g\beta)$，私钥为$\alpha$。
\end{itemize}

\textbf{(2)Alice对消息m加密}\par
\begin{itemize}
	\item 选择一个随机数$k,k\in [1,n-1]$.
	\item 计算点$C_1=(x_1,y_1)=kg$.
	\item 随机选择一个点$P_t=(x_t,y_t)$，计算$C_2=P_t+k\beta$.
	\item 计算密文$C_3=mx_t+y_t$.
	\item 将$(C_1,C_2,C_3)$做为密文发给Bob。
\end{itemize}

\textbf{(3)Bob对密文$(C_1,C_2,C_3)$解密}\par
\begin{itemize}
	\item 使用私钥$\alpha$计算$C_2-\alpha C_1=(x'_t,y'_t)=P'_t$.
	\item 计算$m= \dfrac{(C_3-y'_t)}{x'_t}$，$m$即为解密后的明文。
\end{itemize}
\par
\vspace{0.5cm}

我们简单看看以上过程的正确性：\par
$\alpha C_1=\alpha kg=k \alpha g=k\beta $\par
$(x'_t,y'_t)=C_2 \alpha C_1=P_t +k\beta -k\beta=P_t=(x_t,y_t)$\par
$\dfrac{C_3-y'_t}{x'_t}=\dfrac{mx_t+y_t-y'_t}{x'_t}=m$\par

\paragraph{Diffie-Hellman密钥交换}

下面我们介绍一下如何用椭圆曲线进行DH密钥交换.\par
\begin{itemize}
	\item 选一个素数$p\approx 2^{180}$和两个参数$a,b$，构造$E_p(a,b)$。
	\item 取$E_p(a,b)$的一个生成元$G_1(x_1,y_1)$，使G的阶n是一个非常大的素数。\footnote{G的阶是满足$nG=O$的最小正整数n。}
	\item $E_p(a,b),G,n$公开。
	\item 用户A任选$n_A,n_A \in [1,n-1]$，$n_A$为A的私钥，$P_A=n_A G$是A的公钥。
	\item 用户B任选$n_B,n_B \in [1,n-1]$，$n_B$为B的私钥，$P_B=n_B G$是B的公钥。
	\item A、B双方利用对方的公钥和自身的私钥，即可产生双方共享的密钥$K$,A计算$K=n_AP_B$,B计算$K=n_BP_A$
\end{itemize}

